use std::cmp::min;

pub fn dp_rec_mc(amount: u32) -> u32 {
    let mut dp = vec![amount; amount as usize + 1];
    let coins = vec![1, 2, 5, 10, 20, 50, 100];
    dp[0] = 0;
    for coin in coins.iter() {
        for i in *coin..=amount {
            dp[i as usize] = min(dp[i as usize], dp[(i - coin) as usize] + 1);
        }
    }
    dp[amount as usize]
}
